#include<iostream>
#include<vector>

namespace CloseHsah{
    enum State{
    EMPTY = 0,
    DELETE,
    EXIST
};
template<class T>
struct HachDate{
    T data;
    State state;
    HachDate(const T& x = 0x00):data(x),state(EMPTY)
    {}
};
template<class T>
struct DefaultToFunc{
    int operator()(const T& data)
    {
        return data;
    }
};
template<class T,class ToIntFunc = DefaultToFunc<T>/*默认T为int*/>
class HachTable{
    #define default_table_size 10
private:
    std::vector<HachDate<T>> _table;
    size_t _size;
    ToIntFunc _TtoI;
    int _load = 7;


public:
    HachTable(size_t size = default_table_size)
    {
        _size = 0;
        _table.resize(size);
    }
    bool insert(const T& data)
    {
        if(find(data))
        {
            // std::cout << "insert error ";
            return false;
        }
       if(_size*10 / _table.size() >= _load)
       {
        std::cout << "扩容开始" << std::endl;
            HachTable tmp(_table.size()*2);
            for(auto it : _table)
            {
                if(it.state == EXIST)
                tmp.insert(it.data);
            }
            _table.swap(tmp._table);
       } 
        int hachi = _TtoI(data) % _table.size();
        while(_table[hachi].state == EXIST)
        {
            // if(_table[hachi].data == data)
            // {
            //     return false;
            // }
            ++hachi;
            hachi %= _table.size();
        }
        _table[hachi].state = EXIST;
        _table[hachi].data = data;
        ++_size;
        return true;
    }
    bool erase(const T& data)
    {
        if(!find(data))
        {
            return false;
        }
        int hachi = _TtoI(data)%_table.size();
        // int record = hachi;
        while(_table[hachi].state != EMPTY && _table[hachi].data != data)
        {
            ++hachi;
            hachi %= _table.size();
            // if(hachi == record)
            // {
            //     return false;
            // }
        }
        _table[hachi].state = DELETE;
        --_size;
        return true; 
    }
    bool find(const T& data)
    {
        if(_size == 0)
        {
            return false;
        }
        int hachi = _TtoI(data)%_table.size();
        int record = hachi;
        while(_table[hachi].state != EMPTY && _table[hachi].state != EXIST && _table[hachi].data != data)
        {
            ++hachi;
            hachi %= _table.size();
            if(hachi == record)
            {
                return false;
            }
        }
        if(_table[hachi].state == EMPTY)
        {
            return false;
        }
        return true;
    }
    void print()
    {
        for(int i = 0;i<_table.size();i++)
        {
            if(_table[i].state == EXIST)
            std::cout << _table[i].data << " "; 
        }
        std::cout << std::endl;
    }
};
}
namespace HashBucket{
    template<class T>
    class HashData{
        public:
        T _data;
        HashData* _next;
        HashData(const T& data):_data(data),_next(nullptr){
        }


    };
template<class T>
struct DefaultToFunc{
    int operator()(const T& data)
    {
        return data;
    }
};
    template<class T,class ToIntFunc = DefaultToFunc<T>>
    class HashTable{
        typedef HashData<T> Data;
        private:
        std::vector<Data*> _table;
        int _size;
        ToIntFunc TtoI;
        

        public:
        HashTable(size_t size = 11)
        {
            _size = size;
            _table.resize(_size);
        }
        bool insert(const T& data)
        {
           if(find(data) == true)
           {
               return false;
           }
            int hashi = TtoI(data) % _table.size();
            //找到对应的哈希位置
            if(_table[hashi] == nullptr)
            {
                _table[hashi] = new Data(data);
                return true;
            }
            Data* record = nullptr;
            Data* nowNode = _table[hashi];
            while(nowNode)
            {
                record = nowNode;
                nowNode = nowNode->_next;
            }
            record->_next = new Data(data);
            return true;
            
        }
        bool erase(const T& data)
        {
            if(find(data) == false)
            {
                return false;
            }
            //找到对应的哈希位置
            int hashi = TtoI(data) % _table.size();
            Data* record = nullptr;
            Data* nowNode = _table[hashi];
            while(nowNode)
            {
                if(nowNode->_data == data)
                {
                  if(nowNode == _table[hashi])
                  {
                    _table[hashi] = nowNode->_next;
                    delete nowNode;
                    nowNode = nullptr;
                    return true;
                  }
                  record->_next = nowNode->_next;
                  delete nowNode;
                  nowNode = nullptr;
                  return true;
                }
                record = nowNode;
                nowNode = nowNode->_next;
            }
            std::cerr << "erase error" << std::endl;
            exit(-1);
        }
        bool find(T data)
        {
          int hashi = TtoI(data)%_table.size();
          Data* node = _table[hashi];
          if(node == nullptr)
          {
            return false;
          }
          while(node)
          {
            if(node->_data == data)
            {
              return true;
            }
            node = node->_next;
          }
          return false;
        }
    void print()
    {
        for(int i = 0;i<_table.size();i++)
        {
          if(_table[i] != nullptr)
          {
            Data* node = _table[i];
            while(node)
            {
              std::cout << node->_data << std::endl;
              node = node->_next;
            }
          }
        }
        std::cout << std::endl;
    }

    };

}
